/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.monotone

import java.lang.IllegalArgumentException
import kotlin.math.floor
import kotlin.math.ln

/**
 * An addressable radix heap for (signed) integer keys. The heap stores integer
 * keys sorted according to the [natural ordering][Comparable] of its
 * keys. A radix heap is a monotone heap, especially designed for algorithms
 * (such as Dijkstra) which scan elements in order of nondecreasing keys.
 *
 *
 *
 * The implementation uses arrays in order to store the elements. Operations
 * `insert` and `findMin` are worst-case constant time. The cost of
 * operation `deleteMin` is amortized O(logC) assuming the radix-heap
 * contains keys in the range [0, C] or equivalently
 * [a,a+C]. This implementation views integer values as signed
 * numbers.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @author Dimitrios Michail
 *
 * @param <V>
 * the type of values maintained by this heap
 *
 * @see Serializable
</V> */
class IntegerRadixAddressableHeap<V>(minKey: Int, maxKey: Int) : AbstractRadixAddressableHeap<Int, V>() {
    /**
     * Constructs a new heap which can store values between a minimum and a
     * maximum key value (inclusive).
     *
     * It is important to use the smallest key range as the heap uses O(logC)
     * where C=maxKey-minKey+1 buckets to store elements. Moreover, the
     * operation `deleteMin` requires amortized O(logC) time.
     *
     * @param minKey
     * the non-negative minimum key that this heap supports
     * (inclusive)
     * @param maxKey
     * the maximum key that this heap supports (inclusive)
     * @throws IllegalArgumentException
     * if the minimum key is negative
     * @throws IllegalArgumentException
     * if the maximum key is less than the minimum key
     */
    init {
        if (minKey < 0) {
            throw IllegalArgumentException("Minimum key must be non-negative")
        }
        this.minKey = minKey
        this.lastDeletedKey = minKey
        if (maxKey < minKey) {
            throw IllegalArgumentException("Maximum key cannot be less than the minimum")
        }
        this.maxKey = maxKey

        // compute number of buckets
        val numBuckets: Int
        if (maxKey == minKey) {
            numBuckets = 2
        } else {
            numBuckets = 2 + 1 + (floor(ln(maxKey.toDouble() - minKey) / ln(2.0)).toInt())
        }

        // construct representation
        this.buckets = (java.lang.reflect.Array.newInstance(Node::class.java, numBuckets) as Array<Node?>)
        this.size = 0
        this.currentMin = null
    }

    /**
     * {@inheritDoc}
     */
    override fun compare(o1: Int, o2: Int?): Int {
        if (o1 < o2!!) {
            return -1
        } else if (o1 > o2) {
            return 1
        } else {
            return 0
        }
    }

    /**
     * {@inheritDoc}
     */
    override fun msd(a: Int, b: Int?): Int {
        /*
         * Value equal
         */
        if (a == b) {
            return -1
        }
        /*
         * This is a fast way to compute floor(log_2(a xor b)).
         */
        val axorb: Float = (a xor b!!).toFloat()
        return Math.getExponent(axorb)
    }

    companion object {
        private val serialVersionUID: Long = 1
    }
}
